A conventional network switching appliance receives packets of a flow onto one of several input ports. For each packet, the switching appliance examines parts of the headers of the packet, and from these headers determines the flow to which the packet belongs. For each such flow, the switching appliance may be preconfigured so that it will output packets of that flow onto the predetermined one of the output ports. Once the flow of a packet has been identified, the switching appliance outputs the packet onto the appropriate output port in accordance with how the switching appliance has been preconfigured.
One type of conventional network switching appliance may operate to switch several millions of flows. The switching appliance may receive packets at a 10 Gbps rate or more on each of several input ports, and may output the packets onto several output ports at a 10 Gbps rate or more onto each of one or more output ports. In such a switching appliance, the flow of a packet is determined by a flow key, where the flow key is a concatenation or a combination of the IP source address of the packet, the IP destination address of the packet, the TCP source port of the packet, the TCP destination port of the packet, and other parameters. These identifying values are extracted from the headers of an incoming packet and are concatenated or otherwise combined to form the flow key. A hash algorithm is then used to convert the flow key into a shorter hash value. The hash value is then used as an index into a hash table of hash entries. The hash algorithm may convert multiple different flow keys into the same hash value, so the hash table will be indexed the same way to point to the same hash entry despite the packets being of these different flows. The hash entry stores the full flow key, and also stores or points to or is otherwise associated with certain associated lookup information. The lookup information may, for example, indicate an output port of the switching appliance from which packets of the flow are to be output.
It would be desirable to have a mechanism that speeds up or otherwise improves this lookup operation in a switching appliance.